package com.algrithom.stropr;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 249. 移位字符串分组
 * 
 * @author think
 */
public class Solution3 {
    
    public static void main(String[] args){
        String[] strs = new String[]{"abc","bcd","acef","ze","xyz","az","ba","a","z"};
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.groupStrings1(strs));
    }
    
    private String hash(String str){
        StringBuilder builder = new StringBuilder();
        for (int i = 1; i < str.length(); i++) {
            builder.append((str.charAt(i) - str.charAt(i - 1) + 26) % 26);
        }
        return builder.toString();
    }
    
    public List<List<String>> groupStrings1(String[] strs){
        Map<String,List<String>> map = new HashMap<>();
        for (String e : strs) {
            String hashed = hash(e);
            if (!map.containsKey(hashed)) {
                map.put(hashed,new ArrayList<String>());
            }
            List<String> list = map.get(hashed);
            list.add(e);
        }
        List<List<String>> res = new ArrayList<>();
        for (String key : map.keySet()) {
            res.add(map.get(key));
        }
        return res;
    }
}